\documentclass[a4paper,nofonts]{tufte-handout}

%\usepackage{graphicx}
\usepackage{tikz}

\title[Моделирование процесса передачи биконов]%
{Моделирование процесса передачи биконов}
\author{А. Сафонов, А. Соболевский (ИППИ РАН)}
\date{}

\begin{document}
\maketitle





%-----------------------------------------------------------------
\section{Некоторые сведения о биконах}
\label{sec:beacons}

\emph{Биконом} (от англ. beacon)\marginnote{\exerc Именно этот термин используется в международных стандартах проекта IEEE 802. А что такое IEEE 802 и какие стандарты разработаны в его рамках?}
называется один из служебных пакетов канального уровня. Разумеется формат и содержание этого пакета зависят от протокола, работающего на канальном уровне. Говоря же абстрактно, можно лишь перечислить свойства и функции биконов.

Биконы передаются регулярно и время передачи следующего бикона (или интервал времени, когда бикон может быть передан) известно всем узлам сети.\marginnote{Биконы передаются широковещательно, без квитирования, и, если только не применяется никаких дополнительных мер, передавший бикон узел сети не знает, была ли эта передача успешной.} При этом для передачи используется сигнально-кодовая конструкция, как правило, достаточно робастная, которую заведомо поддерживают все потенциальные адресаты бикона. Эти свойства позволяет биконам выполнять следующие свойства.

Во-первых, биконы служат маячком сети и сигнализируют о ее существовании и свойствах. Во-вторых, биконы несут метку времени (timestamp) и используются узлами сети для синхронизации внутренних часов. В-третьих,\marginnote{Например, с помощью биконов точка доступа сетей Wi-Fi сигнализирует ассоциированым с ней устройствам, находящимся в режиме энергосбережения и потому ``просыпающимся'' только для получения бикона, о необходимости ``проснуться'' и принять новые данные.} биконы служат контейнерами, в которые некоторые сетевые протоколы добавляют свою сигнальную информацию. Таким образом, надежная рассылка биконов чрезвычайно важна, и если достаточно большое число биконов в процессе передачи теряется, работа сети нарушается.




%-----------------------------------------------------------------
\section{Предмет исследования}
\label{sec:subject}
Рассмотрим сеть, работающую по следующим правилам.

Узел, который организует сеть, задает серию моментов времени, которые называют ожидаемым временем передачи бикона (Target Beacon Transmission Time, TBTT). Последовательные моменты TBTT отделены друг от друга равными интервалами времени --- бикон-интервалами, как показано на рис.~\ref{pic:superframe}.

\begin{figure*}[!htbp]
  % \begin{center}
    % \includegraphics[width=\textwidth]{pics/superframe.pdf} 
    \begin{tikzpicture}[>=stealth,font=\footnotesize]
      \draw[ultra thick, gray] (0, 0) -- (0, 2.75) (8, 0) -- (8, 2.75);
      \draw (0, 2.5) node[right] {ТВТТ} (8, 2.5) node[right] {ТВТТ};
      \draw (4, 0) -- (4, 2.125);
      \foreach \x in {.125, .25, ..., 3.875}
        \draw[very thin] (\x, 0) -- (\x, 1);
      \draw[<->] (0, 2) -- (8, 2);
      \draw (4, 2) node[fill=white] {Бикон-интервал};
      \draw[<->] (0, 1.5) -- (4, 1.5);
      \draw (2, 1.5) node[fill=white] {Окно передачи биконов};
      \draw (-1, 1) -- (9, 1) (-1, 0) -- (9, 0);
      \draw (0, 0) -- (0, -.125) node[below] {$0$};
      \draw (4, 0) -- (4, -.125) node[below] {$W$};
      \draw (-1, .5) node {Данные} (6, .5) node {Данные}
      (9, .5) node {};
      \draw (6, 0) node[fill=white] {$\cdots$}
      (6, 1) node [fill=white] {$\cdots$};
    \end{tikzpicture}
  % \end{center}
  \caption[][-\baselineskip]{Структура суперкадра}
  \label{pic:superframe}
\end{figure*}

В каждый момент TBTT каждый из узлов равновероятно выбирает целое значение в интервале от нуля до $W$ ($W \in \mathbb{N}$). Принято говорить, что узлы разыгрывают случайную задержку в \emph{окне\marginnote{Передача \emph{данных} в окне передачи биконов запрещена. В нем могут начинаться только передачи биконов.} передачи биконов}.

Разыграв задержку, узлы начинают обратный отсчет от выбранного значения до нуля. Значение счетчика уменьшается на единицу по прошествии времени $\sigma$, которое будем называть \emph{слотом}.\marginnote{Согласно описанному здесь алгоритму обратный отсчет слотов происходит безотносительно состояния канала (занят или свободен): узел интересуется состоянием канала лишь непосредственно перед началом передачи. Позднее нам встретятся и другие алгоритмы обратного отсчета.} Когда значение счетчика становится равным нулю, узел выполняет прослушивание среды (англ. carrier sensing) и начинает передачу бикона, если канал свободен, или отменяет передачу бикона, если канал оказался занят.




%-----------------------------------------------------------------
\section{Критерии эффективности}
\label{sec:beacons}

Будем искать величину $h(N)$ --- среднее число биконов, успешно переданных в течение бикон-интервала в зависимости от числа $N$ узлов в сети.

Зная эту величину, легко посчитать и вероятность успешной передачи бикона выбранным узлом в течение бикон-интервала, обозначим ее $\alpha(N)$, в зависимости от $N$. Считая все узлы сети идентичными, легко видеть, что\marginnote{\exerc Выразите через $h(N)$ вероятность успешной передачи выбранным узлом хотя бы одного бикона в течение $m$ бикон-интервалов подряд.}

\begin{equation}
	\alpha(N) = \frac{h(N)}{N}.
\end{equation}




%-----------------------------------------------------------------
\section{Математическая модель}
\label{sec:model}

Для оценки искомых величин построим математическую модель, описывающую процесс передачи биконов по описанным выше правилам.

Положим\marginnote{Эти утверждения являются допущениями нашей модели, и поэтому являются источником ошибки (погрешности) при оценке искомых величин.}, что время, необходимое для передачи бикона, равно целому числу слотов, которое обозначим $b$ и будем называть длиной бикона. Предположим также, что длина бикона --- одинакова для всех узлов.

Пусть узел выбрал для начала передачи своего бикона слот $i$. Тогда он передаст его успешно, только если он \emph{единственный} узел, который выбрал слот $i$, и никакой другой узел не начинает передачу своего бикона в слотах $[i−b+1; i−1]$.\marginnote{\exerc Объяснить почему.}

Рассмотрим сеть, состоящую из $N$ узлов, находящихся в радиовидимости друг друга.\marginnote{Требование радиовидимости для всех узлов сети, очевидно, выполняется не всегда, и поэтому оно ограничивает область применимости нашей модели.}

Рассмотрим далее окно передачи биконов как последовательность \emph{блоков}, каждый из которых состоит из нескольких слотов. Блок начинается после передачи бикона и длится до тех пор, пока не закончится передача следующего бикона. Таким образом,\marginnote{Кроме первого и последнего блоков: первый всегда начинается с момента TBTT, а последний может содержать меньше, чем $b$ непустых слотов.} блок состоит из $b$ слотов собственно передачи бикона, которым, возможно, предшествуют несколькими пустых слотов.

\begin{figure}[!htbp]
  \begin{center}
    % \includegraphics[width=\textwidth]{pics/beacon_no_cs.pdf}
    \begin{tikzpicture}[>=stealth,font=\footnotesize]
      \foreach \x in {0, 3.6, 6.6}
      {  \filldraw[gray] (\x, 0) rectangle (\x + .6, .6);
         \filldraw[lightgray] (\x + .6, 0) rectangle (\x + 2.4, .6);}
      \draw (-.6, 0) -- (9.6, 0) (-.6, .6) -- (9.6, .6);
      \foreach \x in {0, .6, ..., 9.6}
        \draw (\x, 0) -- (\x, .6);
      \foreach \x in {0, 2.4, 6, 9}
        \draw (\x, 0) -- (\x, -1);
      \foreach \x in {3.6, 6.6} \draw (\x, 0) -- (\x, -.5);
      \draw[<->] (0, -.75) -- (2.4, -.75);
      \draw (1.2, -.75) node[fill=white] {блок $J - 1$};
      \draw[<->] (2.4, -.75) -- (6, -.75);
      \draw (4.2, -.75) node[fill=white] {блок $J$};
      \draw[<->] (6, -.75) -- (9, -.75);
      \draw (7.5, -.75) node[fill=white] {блок $J + 1$};
      \draw[<->] (0, -.25) -- (2.4, -.25);
      \draw (1.2, -.25) node[fill=white] {$b$ слотов};
      \draw[<->] (3.6, -.25) -- (6, -.25);
      \draw (4.8, -.25) node[fill=white] {$b$ слотов};
      \draw[<->] (6.6, -.25) -- (9, -.25);
      \draw (7.8, -.25) node[fill=white] {$b$ слотов};
      \draw[->] (3.9, 1) node[fill=white] {$i$} -- (3.9, .6);
      \draw[->] (5.7, 1) node[fill=white] {$i + b - 1$} -- (5.7, .6);
      \draw (-.5, .3) node {$\cdots$} (9.5, .3) node {$\cdots$};
    \end{tikzpicture}\\
    \tikz\filldraw[gray,draw=black] (0, 0) rectangle (1.5ex,
    1.5ex);\,: начало передачи бикона,\quad
    \tikz\filldraw[lightgray,draw=black] (0, 0) rectangle (1.5ex,
    1.5ex);\,: тело бикона,\quad
    \tikz\draw (0, 0) rectangle (1.5ex, 1.5ex);\,: пустой слот
  \end{center}
  \caption{Фрагмент окна передачи биконов}
  \label{pic:beacon_no_cs}
\end{figure}

Рассмотрим некоторый блок $J$ и обозначим $i$ номер того слота в блоке, в котором начинается передача бикона, см. рис.~\ref{pic:beacon_no_cs}. Например, для блока $J$ на рис.~\ref{pic:beacon_no_cs} $i = 3$, так как первые два слота в этом блоке оказались пусты.

Запланировать начало передачи своих биконов в $i$-ом слоте могут несколько узлов. Поэтому в каждом блоке может произойти как успешная передачи, так и коллизия.

Среднее число успешно переданных биконов за одно окно, очевидно, зависит не только от числа узлов в сети, но и от размера окна передачи биконов, поэтому можно записать $h(N) = h(N,W)$.

Пусть $h(n,w)$ --- среднее число биконов, успешно переданных за остаток окна $w$, который начинается с $J$-ого блока и длится до конца окна, причем $n$ --- число узлов, запланировавших свои передачи в этом остатке. Пусть $k$ --- число узлов, запланировавших начать передачу бикона в текущем блоке. Пусть $h_s(k,i)$ и $h_c(k,i)$ --- соответственно вероятности успешной передачи бикона и коллизии в текущем блоке с заданными $k$ и $i$. Следуя блок за блоком от начала окна передачи биконов к его концу, можно посчитать среднее число успешно переданных биконов за одно окно рекурсивно:

\begin{eqnarray}
	\lefteqn{h(n,w) = \sum_{i=1}^{w} \sum_{k=1}^{n} h_s(k,i) + {} }\\ 
		& {} + \sum_{i=1}^{w-b} \sum_{k=1}^{n-1} [h_s(k,i)+h_c(k,i)] h(n-k, w-i-b+1).
\end{eqnarray}

В первом слагаемом отражен тот факт, что вероятность успешной передачи бикона равна $h_s(k,i)$. Вторая сумма отражает переход к следующему блоку до тех пор, пока не будет достигнут конец окна передачи биконов. Процесс переходит к следующему блоку с вероятностью $h_s(k,i)$, если передача в рассматриваемом блоке была успешной, и с вероятностью $h_c(k,i)$, если сразу несколько узлов запланировали передачу своих биконов в слоте $i$, т.е. была коллизия.

%Задача свелась к нахождению вероятностей $h_s(k,i)$ и $h_c(k,i)$. Чтобы найти $h_s(k,i)$, рассмотрим текущий блок $J$ в наиболее распространенном случае, когда $i < w-b$. Число способов выбрать $k$ узлов, которые планируют начать передачу в блоке $J$, из $n$ узлов равно $C^n_k = \frac{n!}{k!(n-k)!}$. Число способов выбрать один узел, который начнет свою передачу в $i$-ом слоте $J$-го блока, равно $k$. Число способов выбрать один из $b-1$ оставшихся слотов для каждого из оставшихся $k-1$ узлов в блоке $J$ равно $(b-1)^{k-1}$. Число способов выбрать слоты остальным $n-k$ узлам в остатке окна передачи биконов после блока $J$ равно $(w-i-b+1)^{n-k}$. Всего же число способов назначить $n$ узлам по одному слоту из $w$ слотов равно $w^n$.

%Когда $w-b < i ≤ w$, т.е. текущий блок является последним в окне передачи биконов, в блоке может содержаться менее $b$ занятых слотов. Для подсчета $h_s(k,i)$ в этом случае необходимо заменить $b-1$ на $w-i$, а $k$ положить равным $n$. Теперь можем записать для $h_s(k,i)$ следующее выражение:

Осталось выписать выражения для вероятностей $h_s(k,i)$ и $h_c(k,i)$:\marginnote{\exerc Объясните, как получились такие выражения.}

\begin{equation}
	h_s(k,i) = \left\{ \begin{array}{ll}
		C_k^n k(b-1)^{k-1} \frac{(w-i-b+1)^{n-k}}{w^n}, & i \leq w-b \\
		n \frac{(w-i)^{n-1}}{w^n}, & w-b < i \leq w, k = n \\
		0, &  w-b < i \leq w, k \neq n	
	\end{array} \right .
\end{equation}

%Аналогично рассмотрим блок $J$ для нахождения $h_c(k,i)$. Число способов выбрать один из $b$ слотов для каждого из $k$ узлов равно $b^k$. Необходимо учитывать только те случаи, когда в одном и том же $i$-ом слоте запланировали передачу сразу несколько узлов. Чтобы исключить неколлизионные случаи, необходимо из $b^k$ вычесть число всех случаев, когда в $i$-ом слоте не запланировала передачу ни один узел, и число всех случаев, когда в $i$-ом слоте запланировал передачу только один узел. Число способов выбрать слоты в остатке окна передачи биконов для $n-k$ узлов было найдено выше. Таким образом, для $h_c(k,i)$ получаем следующее выражение:

\begin{equation}
	h_c(k,i) = C_k^n \left[ b^k - (b-1)^k - k(b-1)^{k-1} \right] \frac{(w-i-b+1)^{n-k}}{w^n}.
\end{equation}

Последнее выражение справедливо для случая $i \leq w-b$. Остальные случаи не рассматриваются, так как они не входят в выражение для $h(n,w)$. В итоге мы имеем аналитические выражения для $h_s(k,i)$ и $h_c(k,i)$ и, значит, можем найти и $h(N,W)$. Анализ завершен.\marginnote{\exerc Постройте семейство зависимостей $h(N,W)$ для $N=\{10,\ldots, 50\}$ и $W = \{10, 50, 100, 150\}$.}

\end{document}
